package com.dbh.alg.algorithm.sort;

import java.util.Arrays;

/**
 * 选择排序
 *
 * @author dongbanghui
 * @date 2020/05/03
 */
public class SelectionSort {

    /**
     * 选择排序（从前向后排序）
     * @param arr 待排序数组
     * @param n 排序数据个数
     */
    public static void selectionSort(int arr[], int n){
        for (int i = 0; i < n; i++){
            int minIndex = i;
            for (int j = i + 1; j < n; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if(i != minIndex){
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    /**
     * 选择排序（从后向前排序）
     * @param arr 待排序数组
     * @param n 排序数据个数
     */
    public static void selectionSort2(int arr[], int n) {
        for (int i = n - 1; i >=0; i--) {
            int maxIndex = i;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }
            if (i != maxIndex) {
                int temp = arr[i];
                arr[i] = arr[maxIndex];
                arr[maxIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,6,1,9,0,8,7,5};
        selectionSort2(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }
}
